Search Results

1. E. Hyytiä and J. Virtamo, Near-Optimal Load Balancing in Dense Wireless Multi-Hop Networks, in NGI 2008, 4th Conference on Next Generation Internet Networks, 2008, Krakow, Poland (bib)

   Abstract: We consider the load balancing problem in wireless multi-hop networks. In the limit of a dense network, there is a strong separation between the macroscopic and microscopic scales, and the load balancing problem can be formulated as finding continuous curves (``routes'') between all source-destination pairs that minimize the maximum of the so-called scalar packet flux (``traffic load''). In this paper we re-formulate the problem by focusing entirely on the so-called d-flows (vector flow field of packets with a common destination x) and by looking at the equation these flows have to satisfy. The general solution to this equation can be written in terms of a single unknown scalar function, psi(r,x), related to the circulation density of the d-flow, for which function the optimization task can be presented as a problem of variational calculus. In this approach, we avoid completely dealing with systems of paths and calculating the load distribution resulting from the use of a given set of paths. Once the optimal solution for psi(r,x) is found the corresponding paths are obtained as the flow lines of the d-flows. In the example of a unit disk with uniform traffic demands we are able to find a set of paths which is considerably better than any previously published results, yielding a low maximal scalar flux and an extraordinarily flat load distribution. We further illustrate the methodology for a unit square with comparable improvements achieved.